package qjc.i_图论;

public class i4_实现trie {
    /**
     * 解题思路：实现一个前缀树（Trie，字典树）
     * <p>
     * 前缀树是一种用于高效存储和检索字符串集合的数据结构，特别适合处理前缀相关的操作。
     * <p>
     * 核心思想：
     * - 每个节点代表一个字符，从根到某节点的路径构成一个字符串前缀；
     * - 节点的 children 数组存储其所有可能的子字符（此处假设只含小写字母 a-z）；
     * - 使用布尔值 isEndOfWord 标记该节点是否为某个单词的结尾；
     * - 插入、搜索、前缀匹配的时间复杂度均为 O(m)，m 为字符串长度，与数据集大小无关。
     * <p>
     * 功能说明：
     * 1. insert(word): 逐字符插入，不存在则创建新节点，最后标记单词结尾；
     * 2. search(word): 逐字符查找，若路径存在且最后一个节点标记为结尾，则返回 true；
     * 3. startsWith(prefix): 逐字符查找，只要路径存在即返回 true，不关心是否为单词结尾。
     * <p>
     * 优势：
     * - 高效支持前缀匹配（如自动补全）；
     * - 共享公共前缀，节省空间；
     * - 搜索时间不随词典大小增长。
     * <p>
     * 时间复杂度：
     * - 插入、搜索、前缀查询：O(m)，m 为字符串长度
     * 空间复杂度：O(ALPHABET_SIZE * N * M)，N 为单词数，M 为平均长度
     */

    private TrieNode root;

    public i4_实现trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                node.children[index] = new TrieNode();
            }
            node = node.children[index];
        }
        node.isEndOfWord = true;
    }

    public boolean search(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                return false;
            }
            node = node.children[index];
        }
        return node.isEndOfWord;
    }

    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                return false;
            }
            node = node.children[index];
        }
        return node.isEndOfWord;
    }
}

class TrieNode {
    TrieNode[] children;
    boolean isEndOfWord;

    TrieNode() {
        children = new TrieNode[26];
        isEndOfWord = false;
    }

}